class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ans = []
        paht = []

        def dfs(i,t):
            d = k - len(paht)
            if t < 0 or t > (i*2 - d + 1) * d // 2:
                return
            
            if len(paht) == k:
                ans.append(paht.copy())
                return
            
            for j in range(i,d-1,-1):
                paht.append(j)
                dfs(j-1,t-j)
                paht.pop()

        dfs(9,n)
        return ans